public class BinarySearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    /**
     * 插入一个元素
     * @param key 要插入的元素值
     */
    public boolean insert(int key) {
        if (root == null) {
            root = new TreeNode(key);
            return true;
        }

        TreeNode current = root;
        TreeNode parent;
        while (true) {
            parent = current;
            if (key < current.key) {
                current = current.left;
                if (current == null) {
                    parent.left = new TreeNode(key);
                    return true;
                }
            } else if (key > current.key) {
                current = current.right;
                if (current == null) {
                    parent.right = new TreeNode(key);
                    return true;
                }
            } else { // key already exists
                return false;
            }
        }
    }

    //查找key是否存在
    public TreeNode search(int key) {
        TreeNode current = root;
        while (current != null) {
            if (key == current.key) {
                return current;
            } else if (key < current.key) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }

    //删除key的值
    public boolean remove(int key) {
        TreeNode current = root;
        TreeNode parent = root;
        boolean isLeftChild = true;

        while (current != null && current.key != key) {
            parent = current;
            if (key < current.key) {
                current = current.left;
                isLeftChild = true;
            } else {
                current = current.right;
                isLeftChild = false;
            }
        }

        if (current == null) {
            return false; // 未找到要删除的节点
        }

        // 删除节点分三种情况

        // 第一种情况：被删除节点没有子节点
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }

        // 第二种情况：被删除节点只有一个子节点
        else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }

        // 第三种情况：被删除节点有两个子节点
        else {
            TreeNode successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    // 获取后继节点（右子树中最小的节点）
    private TreeNode getSuccessor(TreeNode node) {
        TreeNode successorParent = node;
        TreeNode successor = node;
        TreeNode current = node.right;

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        if (successor != node.right) {
            successorParent.left = successor.right;
            successor.right = node.right;
        }

        return successor;
    }
}
